1. Field of the Invention
The present invention generally relates to signal decoders, such as, for example decoders of turbodecoder type. More specifically, the present invention relates to specific units used in such decoders, generally called ACS units (“Add-Compare-Select”), which perform additions to provide two data, then compare the two data and select one datum from among the two data.
2. Discussion of the Related Art
One of the aims of digital communications is faultless data transmission. During transmission, the data are submitted to noise that may cause errors on the received data. To improve the reliability upon data transmission, error correction techniques are used. A known error correction technique is convolutional coding. This technique provides an efficient error correction but requires sophisticated decoding techniques.
Error correction codes have a significant technical effect since they enable error correction on data transmitted between a transmitter and a receiver in applications such as telecommunications.
Convolution codes enable the receiver of digital data to properly determine the transmitted data even when errors have occurred in the transmission. Convolution codes introduce redundancies in the data to be transmitted and provide the sequentially transmitted data in packets in which the value of each bit is dependent on preceding bits in the sequence. Thus, when errors occur, the receiver can deduce the original data by retracing the possible sequences of received data.
To further improve the coding efficiency, coding methods comprise interleavers, which mix the order of the bits in the coded packets. Thus, when adjacent bits are altered during transmission, the error is distributed over the entire initial packet and can thus more easily be corrected.
Other improvements may comprise coders which code the data to be transmitted more than once, in parallel or in series. For example, error correction methods which transmit coded data packets for which each packet is formed by the juxtaposition of uncoded initial data, of first coded data resulting from the coding of the initial data by a first coder, and of second coded data resulting from the coding of the initial data by a second coder preceded by an interleaver, are known. Such an error correction method is called a systematic parallel convolutional coding (SPCC).
Such codes are often decoded with an iterative algorithm, called turbodecoding, which is relatively efficient to reach relatively low error rates.
For such codes, an optimal decoding is often a very complex task. Iterative decoding techniques have thus been developed to solve this problem. Rather than immediately determining whether the received data are equal to “0” or to “1”, the receiver assigns to each received datum a value on a scale of several levels representing the probability for the datum to be equal to “1”. A conventional scale, which is usually called the “log-likelihood ratio” LLR, represents each decoded datum x as an integer in a given scale, for example, from 1 to 15. For a received datum r, ratio LLR is determined as follows:
                              LLR          ⁡                      (            x            )                          =                  log          ⁡                      (                                          Pr                ⁡                                  (                                      x                    =                                          1                      /                      r                                                        )                                                            Pr                ⁡                                  (                                      x                    =                                          0                      /                      r                                                        )                                                      )                                              (        1        )            
where Pr(x=1/r) represents the probability for decoded datum x to be equal to “1” for received datum r and Pr(x=0/r) represents the probability for decoded datum x to be equal to “0” for received datum r.
The iterative decoding method receives an input sequence corresponding to probabilities for each received value and outputs corrected probabilities. The iterative decoding is performed by several iterations until it is believed that the corrected probability sufficiently closely represents the transmitted datum.
The value of ratio LLR is then compared with a threshold to determine the value of decoded datum x. For example, the decoded datum is taken as being equal to “1” when ratio LLR is positive, and to “0” otherwise. Ratio LLR thus contains both an information representative of the value of decoded datum x and an information representative of the reliability of the value of the decoded datum.
The calculation algorithm of ratio LLR is based on a treillis similar to that used in the Viterbi algorithm.
FIG. 1 represents an example of a treillis with N states, N being equal to 4 in FIG. 1. Four states Si, i ranging from 1 to 4, are shown along the vertical direction. Different times k, k ranging from 1 to 5, are show along the horizontal direction. Each point Si,k of the treillis represents the i-th state at time k. One state can represent a sequence of a determined number of bits corresponding to the last bits received by the decoder. For a treillis with four states, each state can be associated with one of the sequences (“00”, “01”, “10”, “11”). A branch 5 represents a transition between a state at a time k and a state at a time k+1. The transition from one state to another corresponds to the receiving by the decoder of a datum ideally corresponding to a bit of value “0” or “1”. From a state at a time k, for example, state S2,3, there are thus only two possible transitions to states S3,4 and S4,4 according to whether the received datum is a bit of value “0” or “1”.
In practice, the datum rk received at a time k is an analog datum. A metric γk of the branch corresponding to a possible transition from state Si,k to a state Sm,k+1 is determined for a treillis branch connecting state Si,k and state Sm,k+1. The branch metric corresponds to a distance between received datum rk and datum xk(Si,k, Sm,k+1) which should have been received for the branch. It may be calculated as follows:
                                          γ            k                    ⁢                      (                                                            S                                      i                    ,                                                                                  ⁢                    k                                                  ⁢                                                                              ,                                                          ⁢                              S                                                      m                    ,                                                                                  ⁢                    k                                    +                  1                                                      )                          =                  ⅇ                                                    -                1                                            2                ⁢                                  σ                  2                                                      ⁢                                                                                                r                    k                                    -                                                            x                      k                                        ⁡                                          (                                                                        S                                                      i                            ,                                                                                                                  ⁢                            k                                                                          ,                                                                                                  ⁢                                                  S                                                                                    m                              ,                                                                                                                          ⁢                              k                                                        +                            1                                                                                              )                                                                                                  2                                                          (        2        )            
where σ2 is the noise variance associated with received datum rk.
The calculation algorithm of ratio LLR comprises three main steps.
At a time k, for each state Si,k, i ranging from 1 to N, a forward probability αk(Si,k) of being at state Si,k is calculated as follows:
                                          α            k                    ⁡                      (                          S                              i                ,                                                                  ⁢                k                                      )                          =                              ∑                          l              =              1                        N                    ⁢                                          ⁢                                    ∑                              j                =                0                            1                        ⁢                                                  ⁢                                                            α                                      k                    -                    1                                                  ⁡                                  (                                      S                                                                  l                        ,                                                                                                  ⁢                        k                                            -                      1                                                        )                                            ⁢                                                γ                  k                  j                                ⁡                                  (                                                            S                                                                        l                          ,                                                                                                          ⁢                          k                                                -                        1                                                              ⁢                                          S                                              i                        ⁢                                                                              ,                                                                                                                  ⁢                            k                                                    ⁢                                                                                                                                                                                      )                                                                                        (        3        )            
For each state Si,k, i ranging from 1 to N, a backward probability βk(Si,k) of being at state Si,k is calculated at time k with the following equation:
                                          β            k                    ⁡                      (                          S                              i                ,                                                                  ⁢                k                                      )                          =                              ∑                          l              =              1                        N                    ⁢                                                            ⁢                                          ∑                                  j                  =                  0                                1                            ⁢                                                                                ⁢                                                      β                                          k                      +                      1                                                        ⁡                                      (                                          S                                                                        l                          ,                                                                                                          ⁢                          k                                                +                        1                                                              )                                                  ⁢                                  γ                                      k                    +                    1                                    j                                ⁢                                  (                                                            S                                                                        i                          ,                                                                                                          ⁢                          k                                                ,                                                              ⁢                                          S                                                                        l                          ,                                                                                                          ⁢                          k                                                +                        1                                                                              )                                                                                        (        4        )            
Based on these two probabilities, ratio LLR is calculated as follows:
                              LLR          ⁡                      (                          x              k                        )                          =                  log          ⁢                                                    ∑                                                      (                                          i                      ,                                                                                          ⁢                      1                                        )                                    ∈                                      B                    ⁡                                          (                                              k                        ,                                                                                                  ⁢                        1                                            )                                                                                                                                    ⁢                                                          ⁢                                                                    α                                          k                      -                      1                                                        ⁡                                      (                                          S                                                                        1                          ,                                                                                                          ⁢                          k                                                -                        1                                                              )                                                  ⁢                                                      γ                    k                    1                                    ⁡                                      (                                                                  S                                                                              1                            ,                                                                                                                  ⁢                            k                                                    -                          1                                                                    ,                                                                                          ⁢                                              S                                                  i                          ,                                                                                                          ⁢                          k                                                                                      )                                                  ⁢                                                      β                    k                                    ⁡                                      (                                          S                                              i                        ,                                                                                                  ⁢                        k                                                              )                                                                                                      ∑                                                      (                                          i                      ,                                                                                          ⁢                      1                                        )                                    ∈                                      B                    ⁡                                          (                                              k                        ,                                                                                                  ⁢                        0                                            )                                                                                                                                    ⁢                                                          ⁢                                                                    α                                          k                      -                      1                                                        ⁡                                      (                                          S                                                                        1                          ,                                                                                                          ⁢                          k                                                -                        1                                                              )                                                  ⁢                                                      γ                    k                    0                                    ⁡                                      (                                                                  S                                                                              1                            ,                                                                                                                  ⁢                            k                                                    -                          1                                                                    ,                                                                                          ⁢                                              S                                                  i                          ,                                                                                                          ⁢                          k                                                                                      )                                                  ⁢                                                      β                    k                                    ⁡                                      (                                          S                                              i                        ,                                                                                                  ⁢                        k                                                              )                                                                                                          (        5        )            
where B(k,0) (respectively B(k, 1)) is the set of the possible transitions from a state S1,k−1 to a state Si,k caused by an input datum equal to “0” (respectively, “1”).
The calculation of ratio LLR requires calculation of multiplications and exponential values. These operations are difficult to implement. For this purpose, the following function is introduced:MAX+(x, y)=ln(ex+ey)=MAX(x, y)+ln(1+e−|x−y|)  (6)where term ln(1+e−|x−y|) is a correction value called the offset value. The offset value may be obtained by means of a memory, for example, a ROM, in which are stored values of function ln(1+e−|v|) over a predetermined number of bits for certain values |v| coded over a determined number of bits. Thus:
                                                                        ln                ⁡                                  (                                                            ∑                                              i                        =                        0                                            N                                        ⁢                                                                                  ⁢                                          ⅇ                                              x                        i                                                                              )                                            =                                                MAX                  +                                ⁢                                  (                                                            ln                      ⁡                                              (                                                                              ∑                                                          i                              =                              0                                                                                      N                              -                              1                                                                                ⁢                                                                                                          ⁢                                                      ⅇ                                                          x                              i                                                                                                      )                                                              ,                                                                                  ⁢                                          x                      i                                                        )                                                                                                                        =                                                                            MAX                      +                                        ⁢                                          (                                                                                                    MAX                            +                                                    (                                                                                    ln                              ⁡                                                              (                                                                                                      ∑                                                                          i                                      =                                      0                                                                                                              N                                      -                                      2                                                                                                        ⁢                                                                      ⅇ                                                                          x                                      i                                                                                                                                      )                                                                                      ,                                                                                                                  ⁢                                                          x                                                              N                                -                                1                                                                                                              )                                                ,                                                                                                  ⁢                                                  x                          N                                                                    )                                                        =                  …                                            ⁢                                                                                                                      =                                                                    MAX                                          i                      ∈                                              [                                                  1                          ,                                                                                                          ⁢                          N                                                ]                                                                              +                                ⁡                                  (                                      x                    i                                    )                                                                                        (        7        )            
The following definitions are thus introduced:
                                                        γ              _                        k                    ⁡                      (                                          S                                  m                  ,                  n                                            ,                              S                                  i                  ,                  k                                                      )                          =                  log          ⁡                      (                                          γ                k                            ⁡                              (                                                      S                                          m                      ,                      n                                                        ,                                      S                                          i                      ,                      k                                                                      )                                      )                                              (        8        )                                                                    α              _                        k                    ⁡                      (                          S                              i                ,                k                                      )                          =                  log          ⁡                      (                          S                              i                ,                k                                      )                                              (        9        )            
Term {overscore (αk)}(Si,k) is called the forward state metric for state Si,k, or the forward path metric for state Si,k.{overscore (βk)}(Si,k)=log(βk(Si,k))  (10)
Term {overscore (βk)}(Si,k) is called the backward state metric for state Si,k, or the backward path metric for state Si,k.
As a result:
                                                        α              _                        k                    ⁡                      (                          S                              i                ,                k                                      )                          =                                            MAX                              m                ,                j                                      +                    ⁡                      (                                                                                α                    _                                                        k                    -                    1                                                  ⁡                                  (                                      S                                          m                      ,                                              k                        -                        1                                                                              )                                            +                                                γ                  k                                      -                    j                                                  ⁡                                  (                                                            S                                              m                        ,                                                  k                          -                          1                                                                                      ,                                          S                                              i                        ,                        k                                                                              )                                                      )                                              (        11        )                                                                    β              _                                      k              -              1                                ⁡                      (                          S                              i                ,                                  k                  -                  1                                                      )                          =                                            MAX                              m                ,                j                                      +                    ⁡                      (                                                                                β                    _                                    k                                ⁡                                  (                                      S                                          m                      ,                      k                                                        )                                            +                                                γ                  k                                      -                    j                                                  ⁡                                  (                                                            S                                              i                        ,                                                  k                          -                          1                                                                                      ,                                          S                                              m                        ,                        k                                                                              )                                                      )                                              (        12        )            
The expression of ratio LLR then becomes:
                              LLR          ⁡                      (                          x              k                        )                          =                                                            MAX                                                      (                                          i                      ,                                                                                          ⁢                      m                                        )                                    ∈                                      B                    ⁡                                          (                                              k                        ,                                                                                                  ⁢                        1                                            )                                                                                  +                        ⁡                          (                                                                                          α                      _                                                              k                      -                      1                                                        ⁡                                      (                                          S                                                                        m                          ,                                                                                                          ⁢                          k                                                -                        1                                                              )                                                  +                                                                            γ                      _                                        k                    1                                    ⁡                                      (                                                                  S                                                                              m                            ,                                                                                                                  ⁢                            k                                                    -                          1                                                                    ,                                                                                          ⁢                                              S                                                  i                          ,                                                                                                          ⁢                          k                                                                                      )                                                  +                                                                            β                      _                                        k                                    ⁡                                      (                                          S                                              i                        ,                                                                                                  ⁢                        k                                                              )                                                              )                                -                                                    MAX                                                      (                                          i                      ,                                                                                          ⁢                      m                                        )                                    ∈                                      B                    ⁡                                          (                                              k                        ,                                                                                                  ⁢                        0                                            )                                                                                  +                        ⁡                          (                                                                                          α                      _                                                              k                      -                      1                                                        ⁡                                      (                                          S                                                                        m                          ,                                                                                                          ⁢                          k                                                -                        1                                                              )                                                  +                                                      γ                    k                    0                                    ⁡                                      (                                                                  S                                                                              m                            ,                                                                                                                  ⁢                            k                                                    -                          1                                                                    ,                                                                                          ⁢                                              S                                                  i                          ,                                                                                                          ⁢                          k                                                                                      )                                                  +                                                                            β                      _                                        k                                    ⁡                                      (                                          S                                              i                        ,                                                                                                  ⁢                        k                                                              )                                                              )                                                          (        13        )            
The calculation of the forward and backward metrics {overscore (αk)}(Si,k) and {overscore (βk)}(Si,k) is performed by specific units of the decoder called ACSO (“ADD-COMPARE-SELECT-OFFSET”) units which implement function MAX+.
The calculation of the state metric values must be performed at least at the data receive frequency. The higher the data receive frequency, the more difficult it is to perform these calculation operations in a single data cycle. For this purpose, there exist many configurations of units of ACSO type to reduce the duration of the operation performed by the unit. However, the limiting operating frequencies of the decoder are easily reached. The duration of the operation performed by the ACSO unit is thus a critical factor to be taken into account upon design of a decoder.